package Day007_Collection_泛型_数据结构.Demo06_数据结构;

/*
    数据存储的常用结构有：栈、队列、数组、链表和红黑树

    1. 栈:stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

        特点: 先进后出

        栈的入口、出口的都是栈的顶端位置。

        压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
        弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

    2.队列:queue,简称队，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行取出并删除。

        特点: 先进先出

        队列的入口、出口在两端

    3.数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素

        特点:查找快:通过索引，可以快速访问指定位置的元素
            增删慢:数组长度不能改变,需要创建新数组

    4.链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

        每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

        特点:查询慢:要通过链接的节点,依次从头向后查找
            增删快:只需要修改链接下一个元素的地址值

        单向链表:
                head                                 tail
                a0 [指针域]-->a1 []-->a2 []-->a3 []-->a4 null
        双向链表:
             -->a0 [指针域]<-->a1 []<-->a2 []<-->a3 []<-->a4 []<--

    5.树:
            1. 每一个节点有零个或者多个子节点
            2. 没有父节点的节点称之为根节点，一个树最多有一个根节点
            3. 每一个非根节点有且只有一个父节点

        1).二叉树:
            如果树中的每个节点的子节点的个数不超过2，那么该树就是一个二叉树

        2).二叉查找树:
            1. 左子树上所有的节点的值均小于等于他的根节点的值
            2. 右子树上所有的节点值均大于或者等于他的根节点的值
            3. 每一个子节点最多有两个子树
               取数据:
                   前序:中左右  20  18  23  17  19  22  24
                   中序:左中右  17  18  19  20  22  23  24
                   后序:左右中  17  19  18  20  22  24  23

        3).平衡二叉树:左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
                 左旋 , 右旋

        4).红黑树:一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，可以是红或者黑

                红黑树的特性：
                    1. 每一个节点或是红色的，或者是黑色的。
                    2. 根节点必须是黑色
                    3. 每个叶节点(Nil)是黑色的；（如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点）
                    4. 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
                    5. 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

        表示集合的类有很多,但是每个集合存储数据的数据结构不同,有各自的特点
        ArrayList集合:查询快,增删慢 --> 数据结构是数组
        LinkedList集合:查询慢,增删快 --> 数据结构是链表
        ...
 */

public class Test {
}
